In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the ''i''th row contains only ''i'' elements.

Examples

Notable particular examples include these: *The Bell triangle, whose numbers count the

partitions of a set In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every part ...

in which a given element is the largest singleton * Catalan's triangle, which counts strings of matched parentheses * Euler's triangle, which counts permutations with a given number of ascents *

Floyd's triangle Floyd's triangle is a triangular array of natural numbers used in computer science education. It is named after Robert W. Floyd, Robert Floyd. It is defined by filling the rows of the triangle with consecutive numbers, starting with a 1 in the top ...

, whose entries are all of the integers in order * Hosoya's triangle, based on the

Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...

s * Lozanić's triangle, used in the mathematics of chemical compounds * Narayana triangle, counting strings of balanced parentheses with a given number of distinct nestings *

Pascal's triangle In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Bla ...

, whose entries are the

binomial coefficients In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the te ...

Triangular arrays of integers in which each row is symmetric and begins and ends with 1 are sometimes called generalized Pascal triangles; examples include Pascal's triangle, the Narayana numbers, and the triangle of Eulerian numbers.

Generalizations

Triangular arrays may list mathematical values other than numbers; for instance the

Bell polynomials In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in Faà di Bruno's for ...

form a triangular array in which each array entry is a polynomial. Arrays in which the length of each row grows as a linear function of the row number (rather than being equal to the row number) have also been considered.

Applications

Romberg's method In numerical analysis, Romberg's method is used to estimate the Integral, definite integral \int_a^b f(x) \, dx by applying Richardson extrapolation repeatedly on the trapezium rule or the rectangle rule (midpoint rule). The estimates generate ...

can be used to estimate the value of a

definite integral In mathematics, an integral is the continuous analog of a sum, which is used to calculate areas, volumes, and their generalizations. Integration, the process of computing an integral, is one of the two fundamental operations of calculus,Int ...

by completing the values in a triangle of numbers. The

Boustrophedon transform In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by an "addition" operation, implemented as if filling a triangular array in a boustrophedon (zigzag- or serpentine-l ...

uses a triangular array to transform one

integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...

into another.. In general, a triangular array is used to store any table indexed by two

natural numbers In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

where ''j'' ≤ ''i''.

Indexing

Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates (''i'', ''j'') to a linear

memory address In computing, a memory address is a reference to a specific memory location in memory used by both software and hardware. These addresses are fixed-length sequences of digits, typically displayed and handled as unsigned integers. This numeric ...

. If two triangular arrays of equal size are to be stored (such as in

LU decomposition In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix multiplication and matrix decomposition). The produ ...

), they can be combined into a standard rectangular array. If there is only one array, or it must be easily appended to, the array may be stored where row ''i'' begins at the ''i''th

triangular number A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...

''T_i''. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (i*(i+1)/2), so some optimizations such as using a sequence of shifts and adds are not available.

References

External links